{ "cells": [ { "cell_type": "code", "execution_count": 282, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import pandas as pd\n", "import pulp\n", "import numpy as np\n", "import itertools" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Reading in the data:" ] }, { "cell_type": "code", "execution_count": 283, "metadata": { "collapsed": false }, "outputs": [], "source": [ "df = pd.read_excel(\"availability.xls\")\n", "df = df.replace(\"OK\", 1)\n", "df = df.fillna(0)" ] }, { "cell_type": "code", "execution_count": 287, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Mon 09:00 – 09:30Mon 09:30 – 10:00Mon 10:00 – 10:30Mon 10:30 – 11:00Mon 11:00 – 11:30Mon 11:30 – 12:00Mon 12:00 – 12:30Mon 12:30 – 13:00Mon 13:00 – 13:30Mon 13:30 – 14:00...Fri 13:00 – 13:30Fri 13:30 – 14:00Fri 14:00 – 14:30Fri 14:30 – 15:00Fri 15:00 – 15:30Fri 15:30 – 16:00Fri 16:00 – 16:30Fri 16:30 – 17:00Fri 17:00 – 17:30Fri 17:30 – 18:00
Rhys Lloyd - Alternative Maths0.00.00.00.00.00.00.00.00.00.0...0.00.00.00.00.00.00.00.00.00.0
Europa0.00.00.00.00.00.00.00.00.00.0...0.00.00.00.00.00.00.00.00.00.0
L.A.S.T Resort0.00.00.00.00.00.00.01.00.00.0...0.00.00.00.00.00.00.00.00.00.0
DividedByZeroStudios0.00.00.00.00.00.00.00.00.00.0...0.00.00.00.00.00.00.00.00.00.0
Effervescence0.00.00.00.01.01.00.00.00.00.0...0.00.00.00.00.00.00.01.01.01.0
\n", "

5 rows × 82 columns

\n", "
" ], "text/plain": [ " Mon 09:00 – 09:30 Mon 09:30 – 10:00 \\\n", "Rhys Lloyd - Alternative Maths 0.0 0.0 \n", "Europa 0.0 0.0 \n", "L.A.S.T Resort 0.0 0.0 \n", "DividedByZeroStudios 0.0 0.0 \n", "Effervescence 0.0 0.0 \n", "\n", " Mon 10:00 – 10:30 Mon 10:30 – 11:00 \\\n", "Rhys Lloyd - Alternative Maths 0.0 0.0 \n", "Europa 0.0 0.0 \n", "L.A.S.T Resort 0.0 0.0 \n", "DividedByZeroStudios 0.0 0.0 \n", "Effervescence 0.0 0.0 \n", "\n", " Mon 11:00 – 11:30 Mon 11:30 – 12:00 \\\n", "Rhys Lloyd - Alternative Maths 0.0 0.0 \n", "Europa 0.0 0.0 \n", "L.A.S.T Resort 0.0 0.0 \n", "DividedByZeroStudios 0.0 0.0 \n", "Effervescence 1.0 1.0 \n", "\n", " Mon 12:00 – 12:30 Mon 12:30 – 13:00 \\\n", "Rhys Lloyd - Alternative Maths 0.0 0.0 \n", "Europa 0.0 0.0 \n", "L.A.S.T Resort 0.0 1.0 \n", "DividedByZeroStudios 0.0 0.0 \n", "Effervescence 0.0 0.0 \n", "\n", " Mon 13:00 – 13:30 Mon 13:30 – 14:00 \\\n", "Rhys Lloyd - Alternative Maths 0.0 0.0 \n", "Europa 0.0 0.0 \n", "L.A.S.T Resort 0.0 0.0 \n", "DividedByZeroStudios 0.0 0.0 \n", "Effervescence 0.0 0.0 \n", "\n", " ... Fri 13:00 – 13:30 \\\n", "Rhys Lloyd - Alternative Maths ... 0.0 \n", "Europa ... 0.0 \n", "L.A.S.T Resort ... 0.0 \n", "DividedByZeroStudios ... 0.0 \n", "Effervescence ... 0.0 \n", "\n", " Fri 13:30 – 14:00 Fri 14:00 – 14:30 \\\n", "Rhys Lloyd - Alternative Maths 0.0 0.0 \n", "Europa 0.0 0.0 \n", "L.A.S.T Resort 0.0 0.0 \n", "DividedByZeroStudios 0.0 0.0 \n", "Effervescence 0.0 0.0 \n", "\n", " Fri 14:30 – 15:00 Fri 15:00 – 15:30 \\\n", "Rhys Lloyd - Alternative Maths 0.0 0.0 \n", "Europa 0.0 0.0 \n", "L.A.S.T Resort 0.0 0.0 \n", "DividedByZeroStudios 0.0 0.0 \n", "Effervescence 0.0 0.0 \n", "\n", " Fri 15:30 – 16:00 Fri 16:00 – 16:30 \\\n", "Rhys Lloyd - Alternative Maths 0.0 0.0 \n", "Europa 0.0 0.0 \n", "L.A.S.T Resort 0.0 0.0 \n", "DividedByZeroStudios 0.0 0.0 \n", "Effervescence 0.0 0.0 \n", "\n", " Fri 16:30 – 17:00 Fri 17:00 – 17:30 \\\n", "Rhys Lloyd - Alternative Maths 0.0 0.0 \n", "Europa 0.0 0.0 \n", "L.A.S.T Resort 0.0 0.0 \n", "DividedByZeroStudios 0.0 0.0 \n", "Effervescence 1.0 1.0 \n", "\n", " Fri 17:30 – 18:00 \n", "Rhys Lloyd - Alternative Maths 0.0 \n", "Europa 0.0 \n", "L.A.S.T Resort 0.0 \n", "DividedByZeroStudios 0.0 \n", "Effervescence 1.0 \n", "\n", "[5 rows x 82 columns]" ] }, "execution_count": 287, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df.head()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Transform the data in to a matrix:" ] }, { "cell_type": "code", "execution_count": 288, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "array([[0.0, 0.0, 0.0, ..., 0.0, 0.0, 0.0],\n", " [0.0, 0.0, 0.0, ..., 0.0, 0.0, 0.0],\n", " [0.0, 0.0, 0.0, ..., 0.0, 0.0, 0.0],\n", " ..., \n", " [0.0, 0.0, 0.0, ..., 1.0, 1.0, 1.0],\n", " [0.0, 0.0, 0.0, ..., 0.0, 0.0, 0.0],\n", " [0.0, 0.0, 0.0, ..., 0.0, 0.0, 0.0]], dtype=object)" ] }, "execution_count": 288, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = np.array(df)\n", "A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Create the integer linear problem:" ] }, { "cell_type": "code", "execution_count": 289, "metadata": { "collapsed": false }, "outputs": [], "source": [ "M, N = A.shape # Dimensions\n", "prob = pulp.LpProblem(\"Scheduling\")\n", "x = pulp.LpVariable.dicts(\"x\", itertools.product(range(M), range(N)), \n", " cat=pulp.LpBinary) # Variables" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Constraints:\n", "\n", "$$x_{ij} \\leq A_{ij}$$\n", "\n", "Ie $x_{ij}$ can be 1 iff team $i$ is available in slot $j$." ] }, { "cell_type": "code", "execution_count": 290, "metadata": { "collapsed": false }, "outputs": [], "source": [ "for index in x: \n", " try:\n", " x[index].upBound = float(A[index])\n", " except ValueError: # Seemed to be an artifact in the matrix\n", " x[index].upBound = 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\sum_{i=1}^{M}x_{ij}\\leq1$$\n", "\n", "Ie slot $j$ can only be used by one team." ] }, { "cell_type": "code", "execution_count": 291, "metadata": { "collapsed": false }, "outputs": [], "source": [ "for slot in range(N): \n", " prob += sum(x[(team, slot)] for team in range(M)) <= 1 " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\sum_{j=1}^{N}x_{ij}=1$$\n", "\n", "Ie team $i$ uses exactly one slot." ] }, { "cell_type": "code", "execution_count": 292, "metadata": { "collapsed": true }, "outputs": [], "source": [ "for team in range(M): \n", " prob += sum(x[(team, slot)] for slot in range(N)) == 1 " ] }, { "cell_type": "code", "execution_count": 293, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 293, "metadata": {}, "output_type": "execute_result" } ], "source": [ "prob.solve(pulp.GLPK())" ] }, { "cell_type": "code", "execution_count": 294, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'Optimal'" ] }, "execution_count": 294, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pulp.LpStatus[prob.status]" ] }, { "cell_type": "code", "execution_count": 295, "metadata": { "collapsed": false }, "outputs": [], "source": [ "solution = []\n", "for company in range(M):\n", " for slot in range(N):\n", " if x[(company, slot)].value() == 1:\n", " solution.append([df.index[company], df.columns[slot]])\n", "df = pd.DataFrame(solution, columns=[\"Company\", \"Time slot\"])" ] }, { "cell_type": "code", "execution_count": 296, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " Company Time slot\n", "14 Apollo Tue 16:30 – 17:00\n", "17 Coding Cymraeg Thu 13:30 – 14:00\n", "23 Complexus Tue 10:00 – 10:30\n", "3 DividedByZeroStudios Mon 17:30 – 18:00\n", "4 Effervescence Fri 17:30 – 18:00\n", "1 Europa Thu 13:00 – 13:30\n", "11 F.E.J.L. Tue 15:00 – 15:30\n", "12 Ferdie Amor Wed 12:30 – 13:00\n", "16 Framtak Tue 17:30 – 18:00\n", "15 FridgeVentory Tue 17:00 – 17:30\n", "30 Generic Group Tue 16:00 – 16:30\n", "26 GeoCampus Tue 11:30 – 12:00\n", "5 Green and Russian Standard Fri 16:30 – 17:00\n", "19 JALE Mon 16:00 – 16:30\n", "27 JEM'D Fri 16:00 – 16:30\n", "7 J^2AG Wed 16:30 – 17:00\n", "2 L.A.S.T Resort Mon 12:30 – 13:00\n", "29 MACT enterprises Tue 12:30 – 13:00\n", "10 MBAS Thu 17:30 – 18:00\n", "21 MRJL Mon 15:30 – 16:00\n", "8 Merge Wed 09:00 – 09:30\n", "13 MyTime Tue 15:30 – 16:00\n", "22 Noteable Mon 17:00 – 17:30\n", "20 Oakheart Mon 15:00 – 15:30\n", "24 PoshFit Tue 10:30 – 11:00\n", "25 ReCollect Tue 11:00 – 11:30\n", "0 Rhys Lloyd - Alternative Maths Wed 13:30 – 14:00\n", "6 Room 1 Tue 14:00 – 14:30\n", "9 StockSensors Fri 11:30 – 12:00\n", "28 Swigg Tue 12:00 – 12:30\n", "18 The Cyps Mon 16:30 – 17:00\n", "31 Ticket Tiger Mon 13:00 – 13:30\n" ] } ], "source": [ "print(df.sort_values(by=\"Company\"))" ] }, { "cell_type": "code", "execution_count": 297, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
CompanyTime slot
9StockSensorsFri 11:30 – 12:00
27JEM'DFri 16:00 – 16:30
5Green and Russian StandardFri 16:30 – 17:00
4EffervescenceFri 17:30 – 18:00
2L.A.S.T ResortMon 12:30 – 13:00
31Ticket TigerMon 13:00 – 13:30
20OakheartMon 15:00 – 15:30
21MRJLMon 15:30 – 16:00
19JALEMon 16:00 – 16:30
18The CypsMon 16:30 – 17:00
22NoteableMon 17:00 – 17:30
3DividedByZeroStudiosMon 17:30 – 18:00
1EuropaThu 13:00 – 13:30
17Coding CymraegThu 13:30 – 14:00
10MBASThu 17:30 – 18:00
23ComplexusTue 10:00 – 10:30
24PoshFitTue 10:30 – 11:00
25ReCollectTue 11:00 – 11:30
26GeoCampusTue 11:30 – 12:00
28SwiggTue 12:00 – 12:30
29MACT enterprisesTue 12:30 – 13:00
6Room 1Tue 14:00 – 14:30
11F.E.J.L.Tue 15:00 – 15:30
13MyTimeTue 15:30 – 16:00
30Generic GroupTue 16:00 – 16:30
14ApolloTue 16:30 – 17:00
15FridgeVentoryTue 17:00 – 17:30
16FramtakTue 17:30 – 18:00
8MergeWed 09:00 – 09:30
12Ferdie AmorWed 12:30 – 13:00
0Rhys Lloyd - Alternative MathsWed 13:30 – 14:00
7J^2AGWed 16:30 – 17:00
\n", "
" ], "text/plain": [ " Company Time slot\n", "9 StockSensors Fri 11:30 – 12:00\n", "27 JEM'D Fri 16:00 – 16:30\n", "5 Green and Russian Standard Fri 16:30 – 17:00\n", "4 Effervescence Fri 17:30 – 18:00\n", "2 L.A.S.T Resort Mon 12:30 – 13:00\n", "31 Ticket Tiger Mon 13:00 – 13:30\n", "20 Oakheart Mon 15:00 – 15:30\n", "21 MRJL Mon 15:30 – 16:00\n", "19 JALE Mon 16:00 – 16:30\n", "18 The Cyps Mon 16:30 – 17:00\n", "22 Noteable Mon 17:00 – 17:30\n", "3 DividedByZeroStudios Mon 17:30 – 18:00\n", "1 Europa Thu 13:00 – 13:30\n", "17 Coding Cymraeg Thu 13:30 – 14:00\n", "10 MBAS Thu 17:30 – 18:00\n", "23 Complexus Tue 10:00 – 10:30\n", "24 PoshFit Tue 10:30 – 11:00\n", "25 ReCollect Tue 11:00 – 11:30\n", "26 GeoCampus Tue 11:30 – 12:00\n", "28 Swigg Tue 12:00 – 12:30\n", "29 MACT enterprises Tue 12:30 – 13:00\n", "6 Room 1 Tue 14:00 – 14:30\n", "11 F.E.J.L. Tue 15:00 – 15:30\n", "13 MyTime Tue 15:30 – 16:00\n", "30 Generic Group Tue 16:00 – 16:30\n", "14 Apollo Tue 16:30 – 17:00\n", "15 FridgeVentory Tue 17:00 – 17:30\n", "16 Framtak Tue 17:30 – 18:00\n", "8 Merge Wed 09:00 – 09:30\n", "12 Ferdie Amor Wed 12:30 – 13:00\n", "0 Rhys Lloyd - Alternative Maths Wed 13:30 – 14:00\n", "7 J^2AG Wed 16:30 – 17:00" ] }, "execution_count": 297, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df.sort_values(by=\"Time slot\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python [default]", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.2" } }, "nbformat": 4, "nbformat_minor": 1 }